# Expected Value

• 2026년 6월 29일 알고리즘
  추가 설명 — quickselect는 왜 평균 O(n)인가

  선택 문제 본문이 '대부분 O(n)'으로 넘어간 quickselect의 평균 시간을 기댓값 점화식으로 엄밀히 따진다. quick sort와 달리 한쪽으로만 재귀하기 때문에 E(n)에 max 항이 생기고, 이를 상계로 풀면 E(n) ≤ 4n = O(n)이다.

• 2026년 6월 27일 알고리즘
  quick sort — 최악 O(n²)인데 평균은 왜 O(n log n)인가

  quick sort는 pivot으로 배열을 가르는 분할 정복이다. 두 포인터 분할 과정을 보고 최선 O(n log n)과 최악 O(n²)이 갈리는 지점을 짚는다. 핵심은 평균 분석이다. 기댓값 점화식 E(n)을 세워 평균이 Θ(n log n)임을 유도한다.